package org.kth.dks.dks_node;

import java.util.LinkedList;

import org.kth.dks.dks_comm.DKSRef;
import org.kth.dks.util.MathMisc;

public class RoutingTree {
    int  a_levels;
    int  a_k_factor;
    long a_adrRange;
    DKSRef a_myRef;
    private LevelEntry [][]tree;

    public RoutingTree(long adrRange, int k_factor, int levels, DKSRef ref){

	a_levels    = levels;
	a_k_factor  = k_factor;
	a_adrRange  = adrRange;
	a_myRef     = ref;


	// I make the vector one step larger to simplify access of the
	// different levels.
	tree = new LevelEntry[a_levels+1][a_k_factor];

	for(int l = 1; l <= a_levels ; l ++){
	    for(int j = 0; j < k_factor ; j++){
		long tmp = MathMisc.nThroughKPowerL(adrRange, a_k_factor, l);
		long begin = MathMisc.modPlus(ref.getID(), j * tmp, adrRange);
		long end   = MathMisc.modPlus(ref.getID(), (j+1) * tmp, adrRange);
		tree[l][j] = new LevelEntry(begin, end, ref);
	    }
	}
    }

    // A new node is found. The table is checked to see if the node is a better candidate
    // for any of the intervals in the table.
    public void foundNewNode(DKSRef ref){
	for(int l = 1; l <= a_levels ; l ++){
	    for(int j = 0 ; j < a_k_factor ; j ++){
		LevelEntry tmp = tree[l][j];
		// These are just for making the calls shorter in number of chars
		long curDistance = MathMisc.distanceClockWise(tmp.a_begin, tmp.a_responsible.getID(),a_adrRange);
		long newDistance = MathMisc.distanceClockWise(tmp.a_begin, ref.getID(),a_adrRange);

		// The best node for an interval is:
		//
		// .. the responsible for interval In(l,m) is chosen
		// to be the first node encountered, moving in clockwise direction
		// starting at the begining of the interval... HICSS 2005 paper by Ali.
		//
		// So, if the new node is shorter in distance, moving clockwise on the ring than
	        // the current element, replace the current element.

		if (curDistance>newDistance)
		    tmp.a_responsible = ref;
	    }
	}
}

    // A node is lost. Every instance of the node found in the
    // table is replaced by myRef.
    // This will result in a faulty table. In order to fix the
    // table, the foundNewNode method should be invoced
    // with all nodes known to the node. Returns true if the lost node
    // was present in the routingtable and thus the routingtable
    // has to be fixed.
    public boolean  nodeLost(DKSRef ref){
	boolean ans = false;
	for(int l = 1; l <= a_levels ; l ++){
	    for(int j = 0 ; j < a_k_factor ; j ++){
		LevelEntry tmp = tree[l][j];
		if(tmp.a_responsible.equals(ref)){
		    tmp.a_responsible = a_myRef;
		    ans = true;
		}
	    }
	}
	return ans;

    }

    public LinkedList toList(){
	LinkedList lst = new LinkedList();
	for(int l = 1; l <= a_levels ; l ++){
	    for(int j = 0 ; j < a_k_factor ; j ++){
		LevelEntry tmp = tree[l][j];
		lst.add(tmp.a_responsible);
	    }
	}
	return lst;
    }

    DKSRef getIntervalResp(long target){
	DKSRef ans = a_myRef;
	for(int l = 1; l <= a_levels ; l ++){
	    for(int j = 0 ; j < a_k_factor ; j ++){
		LevelEntry tmp = tree[l][j];
		if(MathMisc.belongsToI(target, tmp.a_begin, tmp.a_end, a_adrRange))
		    ans = tmp.a_responsible;
	    }
	}
	return ans;
    }


    long getIntervalStart(long target){
	long start = target;
	for(int l = 1; l <= a_levels ; l ++){
	    for(int j = 0 ; j < a_k_factor ; j ++){
		LevelEntry tmp = tree[l][j];
		if(MathMisc.belongsToI(target, tmp.a_begin, tmp.a_end, a_adrRange))
		    start = tmp.a_begin;
	    }
	}
	return start;
    }

    public String toString(){
	String ans = "";
	for(int l = 1; l <= a_levels ; l ++){
	    ans += l + " :: ";
	    for(int j = 0 ; j < a_k_factor ; j ++){
		LevelEntry tmp = tree[l][j];
		ans += "\t"+ tmp.a_begin + " - " + tmp.a_end + " = " + tmp.a_responsible.getID();
	    }
	    ans += "\n" ;
	}

	return ans;
    }


    public long getBegin(int l, int i){
	return tree[l][i].a_begin;
    }

    public long getEnd(int l, int i){
	return tree[l][i].a_end;
    }

    public DKSRef getResponsible(int l, int i){
	return tree[l][i].a_responsible;
    }

    public int getLevels(){
	return a_levels;
    }

    public int getKfactor(){
	return a_k_factor;
    }

    class LevelEntry{
	public long    a_begin       = -1;
	public long    a_end         = -1 ;
	public DKSRef a_responsible = null;
	LevelEntry(long begin, long end, DKSRef resp){
	    a_begin       = begin;
	    a_end         = end;
	    a_responsible = resp;
	}
	LevelEntry(){;}
    }

}


